The present invention relates to the field of digital printing and particularly to the performance of anti-aliasing for quality enhancement of the printed picture in the application of variable printing.
In the scope of the present invention, anti-aliasing (AA) is a method for solving quality problems resulting from printing graphic elements in relatively low resolutions. Printing resolutions that are low enough to benefit from this enhancement are in the range of 240-600 DPI.
Printing systems relevant for the suggested enhancement are those with color depth per pixel greater than 2 levels per color plane. For example, suppose a printing machine uses 4 color planesxe2x80x94cyan, magenta, yellow and black (CMYK). If for each pixel, any of C, M, Y and K components can only be printed as either 0% color or 100% color, then this machine is not relevant for the anti-aliasing method suggested in the present invention. If, however, any of the color components can have more than 2 values (for example 16 or 256 different values), then anti-aliasing as suggested can be applied.
In general, anti-aliasing is a process aimed at overcoming the resolution limitation imposed by the printing machine, by getting more spatial graphic information than what is allowed by the printing resolution. The excess spatial information is then transformed into the color space, in a way that fools the eye to perceive more details. A simpler definition of anti-aliasing is reducing the undesirable stair-step pattern along the edges of images printed on low-resolution printing device. Typically, anti-aliasing involves reducing the intensity of intermediate pixels, to give the appearance of a smooth line or edge.
A better understanding of the anti-aliasing process may be attained by the following detailed description and examples in FIGS. 1 and 2:
When rasterizing graphic data for the purpose of printing, the rasterization is done to a resolution that is higher than the printing resolution, for example, 4 times higher at each direction x and y). That is, if printing is done at 300 psi, rasterization will be done to 1200 dpi. Each printed pixel will thus be represented by a matrix of 4xc3x974 pixels in the image raster (e.g. matrix 14 in FIG. 2).
Following that, a pass is made over the entire detailed raster data (1200 dpi). Each 4xc3x974 matrix is averaged to a single color value. The averaging may be a simple sum of all 16 values divided by 16, or any other, more sophisticated known filter. Today, the simple approach is mostly used. The exact averaging algorithm used does not have much influence on the implementation of the present invention.
When the element is not monochromatic, but has several color components (like RGB or CMYK) the process takes place for each color component in the picture (Cyan, Magenta etc.), independently. The present invention will be described only in reference to the monochromatic printing. However, anything said could easily be expanded to the polychromatic case, where each pixel is defined by several color components like: RGB, CMYK, etc.
FIG. 1 is an example of an upper case letter xe2x80x98Ixe2x80x99 10, printed with tint color (100%) surrounded by gray background of 20% 12. No anti-aliasing has been performed.
FIG. 2 shows the same example, but here, anti-aliasing has been performed, creating gray levels that have not existed in the original image. For example, the value of 10% tint in the lower right pixel 16 has been derived by averaging the {fraction (4/16)} pixels having 100% tint with the {fraction (12/16)} pixels having 20% tint. Thus: 10030xc2xc+20+xc2xe=40. As a result, the letter xe2x80x98Ixe2x80x99 in FIG. 2 will have a smoother perceived outline 18.
The process of preparing a page for printing is the pre-press process that includes, amongst others, the RIP (Raster Image Processing) stage that creates a raster representation of the page. The raster representation is the definition of the color of each pixel in the printing resolution.
In the process of RIPping, a hardware or software module called xe2x80x98RIPxe2x80x99 gets a non-raster representation of the complete page. A page description file containing such a representation is created by an application that assembles a page from its components: text, graphics and scanned images. Such an application could be QuarkXpress, available from Quark, Inc. of Denver, Colo. for example. The page description file describes a page in a Page description Language (PDL) such as PostScript, available from Adobe Systems Inc. of San Jose, Calif. The raster generated by the RIP can be stored in any raster format file, such as Scitex CT and I.W, as used by Scitex Corporation of Herzlia, Israel. Alternately, it can be held in memory buffers from which it is printed without being stored on disk.
It is important to not that time needed for RIPping a complex page will usually be much longer than the time it takes to print a single copy of the same page by the printing machine. In the case of conventional (non-variable) printing, this is not significant, since a single (lengthy) RIP operation will yield the printing of many (hundreds, thousands, or more) copies of the page.
With the rising of digital technology, where pages are printed directly from a computer data stream, without involving a pre-set medium such as film or plate, the printing device has no overhead in having each printed page different from its predecessor. This provides the opportunity for variable printing. The ultimate implementation of this technology enables the printing of a unique copy for each recipient of the printed material, tailored according to his/her measurements.
For example: A motor company, that manufactures dozens of models, wants to send advertising brochures in direct mail. Instead of sending a comprehensive and expensive brochure containing a lot of irrelevant information to a certain recipient (like too expensive car, station wagon to a bachelor, etc.), a unique brochure will be assembled for each recipient. For this, available personal information can be used, like place of residence, sex, education level, economic status, marital status and even hobbies and more. Part of this information can be attained from various database owners. Thus, a brochure will be assembled for each recipient, containing only relevant information, as well as additional specific information like a map illustrating the location of the dealers nearest to the recipient. In order to increase the impact, some text may be addressed to the recipient by name.
It is evident that in a case like the one described, where an advertiser in the USA might wish to print several millions of copies, the model introduced above for RIPping may be very problematic. RIPping each of those pages separately can take an unreasonable amount of time, even using a very fast computer. For this purpose, an enhanced model was developed to enable the processing of pages to keep pace with the speed of the digital-printing machine.
This model assumes that even though each page is unique, it may contain graphic elements that are used by other pages.
In the example of the car brochures, many recipients, though not all, will get the picture of a specific car, along with the text accompanying it. All recipients from a certain area will get the same map for the dealers, etc.
The collection of all instances of a document to be printed (brochure in the above example) is called a Printing Job, and is described by a Job Description file that comprises information about all the pages and all the graphical elements participating in all the instances.
FIG. 3 describes schematically a prior-art system designed to perform a more efficient processing of pages for digital printing.
First, Job description file 100 is fed into RIP 110. RIP 110 identifies all the elements participating in all the pages contained in the Job. Each element is RIPped separately and its raster representation stored on disk 160 or, in rare cases, in memory. Scitex CT and LW raster formats are suitable for such storage. In addition, for each page to be printed, a xe2x80x98Page Listxe2x80x99 120 is assembled, containing indication of all the elements composing this page and the exact position of each element on the page. The elements on the Page List are organized by order of appearancexe2x80x94if two elements intersect, the latter will cover the former on the printed page.
During printing, the Page List 120 is processed by hardware or software module 130 called xe2x80x98Combinerxe2x80x99. The Combiner 130 reads all the raster elements participating in a page from disk 160 (or memory) and combines them into page pixel-map 140, according to the Page List directives, to be stored in a rasterized pages storage 170 or to be printed by a digital printing machine 150. The Combiner 130 has relatively little manipulation to do over the graphic data, since the data has already been rasterized to printing resolution. An example of a Combiner is PrintStreamer II, provided by BARCO Graphics NV of Gent, Belgium.
Following is a general description of a Combiner""s 130 mode of operation:
Assume that we have a frame buffer large enough to contain the raster representation of an entire page. The list of participating elements is read sequentially by the Combiner 130 and each element is copied, in its turn, to the buffer, as follows. The offset of the first row is calculated, using the element position on the page. Then, each row of the element is copied into the buffer (number of pixels being the width of the element) and the offset of the next row is calculated by adding the buffer width to the offset of the current row.
A raster element page (text passage, graphic segment or scanned image), designated to be combined into a printed page, is defined in a rectangular domain, which is the enclosing rectangle to all graphics in the element. However, the elements"" graphics does not necessarily cover the entire rectangular area. The rectangular domain may contain areas in which no graphics were xe2x80x98paintedxe2x80x99 at all. If such an element is positioned over another graphic element, the graphics of the lower element should show through the xe2x80x98unpaintedxe2x80x99 areas of the upper element.
For example, if the element is a text passage written in black, it may be positioned on the final page in various combinations; it may be placed over a pink-tinted area or over a scanned photograph, etc. In any such case, it should be assured that in the spaces between letters, as well as in the unpainted portions of the letters themselves, the graphic information below the text would show. This graphic information may, naturally, be different for every instance in which this text is placed on a page.
For this reason, the format containing the variable raster element should have a clear definition of the areas in which, during combining, the xe2x80x98lowerxe2x80x99 graphic data should be unaltered. These areas are referred to as the xe2x80x98backgroundxe2x80x99 areas of the raster element. In the cases in which the raster element is held as a Scitex LW file, these areas can be defined by a special color index.
The RIP can recognize background areas as areas to which there was no graphic reference in the input file (PostScript, for example) and, if it creates a Scitex LW, it can paint these areas with a color that has a pre defined index designated for this purpose.
Returning to the Combiner 130, its mode of operation may be enhanced, so that it may handle properly background pixels.
When the Combiner combines a raster element, whenever it encounters a background pixel, it will not copy it to the frame buffer, but skip to the next pixel, both in the element and the frame buffer. Thus, the pixel color in that location in the frame buffer will be unchanged, still holding the color of the element below.
The problem, to which the present invention is directed, arises if anti-aliasing is attempted at the stage of rasterizing a variable element. From the previous explanation it can easily be understood that anti-aliasing requires, relatively, a lot of computing resources. This is the reason that motivates the performance of anti-aliasing at the stage of the RIP 110 (once per element) and not at the stage of the Combiner 130 (once per printed instance of an element).
In other words, in order to save time at the combine stage, we would like to RIP each element to a resolution 4 times higher (for example) and then immediately perform anti-aliasing to get a raster in the final printing resolution.
The problem arises from the fact that some areas in the element are background areas. Suppose we look at a 4xc3x974 matrix that will be reduced to a single pixel by anti-aliasing.
Analyzing this matrix yields one of three possible outcomes for each print-resolution pixel to be created:
a) Opaquexe2x80x94The area of the matrix is entirely painted. In this case there is no problem; averaging should be done according to the above explanation. The resulting averaged pixel is Opaque.
b) Backgroundxe2x80x94The area covered by the matrix is entirely background area. Here again there is no problem. The averaged pixel resulting from this matrix should also be considered background area. When combining, a pixel from a lower element may show, and we can assume that it had been properly anti-aliased.
c) Semi-Backgroundxe2x80x94The area covered by the matrix is partly painted and partly background. This is the problematic case. We would have liked to use all the color values in that area to make the averaging. However, at this stage, only part of the data is available, that is, the color of the painted area. The color in the background area will only be known at the combining stage, when we can read the color of the element underneath. Furthermore, the color underneath may be different each time the same element is combined (if it is put on top of different elements) and therefore, the resulting averaged color of the pixel could be different every time it is combined.
A method for solving the anti-aliasing problem for display purposes is disclosed in the article xe2x80x9cAnti-aliasing and Transparencyxe2x80x9d by Chris Lilley (incorporated herein as reference), as one of a series of article under the title: xe2x80x9cNot Just Decoration: Quality Graphics for the Webxe2x80x9d (http://www.w3.org/Conference/WWW1/Pagers/53/gq-bostom.html). The article uses a similar idea of defining three levels of transparency for each pixel.
The present invention relates to the field of digital printing, and particularly to the performance of anti-aliasing for quality enhancement of the printed picture in the application of variable printing.
In one aspect of the present invention there is suggested a method for building a raster representation of an anti-aliased color or monochromatic page for digital printing, the page comprising a plurality of elements, the method comprising the steps of:
Rasterizing each of the plurality of elements to a format comprising, for each pixel of the element: color value and binary background attribute.
Anti-aliasing each of the rasterized elements to produce pixels with background factors, each background factor having a value of Opaque, Background or one of a series of Semi-Background values;
Saving the background factors as part of the element""s data file or as a separate data structure.
Composing the page, or sequentially composing portions of the page, by placing the anti-aliased elements into a page pixel map sequentially, where the value of each page pixel in the page pixel map is calculated based on:
the value of the corresponding element""s pixel,
the background factor of the corresponding element""s pixel and
the previous value of the page pixel.
In another aspect of the present invention, there is provided an apparatus for building a raster representation of an anti-aliased color or monochromatic page for digital printing, the page comprising a plurality of elements, the apparatus comprising:
Storage means for storing rasterized page elements and a background factor for each pixel of each of the elements, the background factor having one of the values: Opaque, Background or one of a series of Semi-Background values.
Electronic means, coupled to the storage means, for reading the rasterized page elements and the background factors into memory.
A frame buffer, coupled to the electronic means, for holding pixel values, background factors and original pixel values for an entire page or a portion thereof.
Processing means coupled to the frame buffer, operable to:
Clear the frame buffer.
Sequentially render each of the plurality of element into the frame buffer, the rendering comprising the steps of:
Skipping pixels for which the background factor has the value Background.
Writing both pixel value and background factor to the frame buffer, when the background factor has a Semi-Background value.
Writing original pixel value and clearing the background factor and the pixel value in the frame buffer, when the background factor has the value Opaque.
Merging means such as a look-up table, coupled to the frame buffer, operable to receive original pixel value, background factor and pixel value from the frame buffer and merge them to a single pixel value.
Output means coupled to the merging means, operable to deliver the merged pixel values from the merging means to a memory storage or disk storage, or directly to a digital printing engine.
In another aspect of the present invention, there is provided an apparatus for building a raster representation of an anti-aliased color or monochromatic page for digital printing, the page comprising a plurality of elements, the apparatus comprising:
Storage means for storing rasterized page elements and a background factor for each pixel of each of the elements, the background factor having one of the values: Opaque, Background or one of a series of Semi-Background values.
Electronic means, coupled to the storage means, for reading the rasterized page elements and the background factors into memory.
A first frame buffer, coupled to the electronic means, for holding original pixel values for an entire page or a portion thereof.
A second frame buffer, coupled to the electronic means, for holding background factors and pixel values of pixels for an entire page or a portion thereof.
Processing means coupled to the first and second frame buffers, operable to:
Clear both frame buffers;
Sequentially render each of the plurality of element into both frame buffers, the rending comprising:
Skipping, in both frame buffers, pixels for which the background factor has the value Background.
Writing both pixel value and background factor into the second frame buffer when the background factor has a Semi-Background value.
Writing original pixel value into the first frame buffer and clearing the pixel location in the second frame buffer, when the background factor has the value Opaque.
Merging means such as a look-up table, coupled to both frame buffers, operable to receive original pixel values from the first frame buffer and background factors and pixel values from the second frame buffer, and merge them to a single pixel value.
Output means coupled to the merging means, operable to deliver the merged pixel values from the merging means to a memory storage or disk storage, or directly to a digital printing engine.